#include "main/utils.h"
#include <numeric>
using namespace std;

class Solution {
  public:
    void rotate(vector<int>& nums, int k) {
      int len = nums.size();
      k = k % len;
      vector<int> output(nums.begin() + (len - k), nums.end());
      output.insert(output.end(), nums.begin(), nums.begin() + (len - k));
      nums = output;
    }

    void rotate1(vector<int>& nums, int k) {
      int len = nums.size();
      vector<int> tmp(len);
      for (int i = 0; i < len; ++i) {
        tmp[(i + k) % len] = nums[i];
      }
      nums.assign(tmp.begin(), tmp.end());
    }

    void rotate2(vector<int>& nums, int k) {
      int len = nums.size();
      k %= len;
      int cnt = gcd(k, len);
      for (int start = 0; start < cnt; ++start) {
        int cur = start;
        int pre = nums[start];
        do {
          int next = (cur + k) % len;
          swap(nums[next], pre);
          cur = next;
        } while (start != cur);
      }
    }

    void reverse(vector<int>& nums, int start, int end) {
      while (start < end) {
        swap(nums[start], nums[end]);
        ++start;
        --end;
      }
    }
    void rotate3(vector<int>& nums, int k) {
      int len = nums.size();
      k %= len;
      reverse(nums, 0, len - 1);
      reverse(nums, 0, k - 1);
      reverse(nums, k, len - 1);
    }
};

int main() {
  vector<int> input = {1, 2, 3, 4, 5, 6, 7};
  int k = 2;
  Solution su;
  su.rotate(input, k);
  printVec("output", input);

  input = {1, 2, 3, 4, 5, 6, 7};
  su.rotate1(input, k);
  printVec("output1", input);

  input = {1, 2, 3, 4, 5, 6, 7};
  su.rotate2(input, k);
  printVec("output2", input);

  input = {1, 2, 3, 4, 5, 6, 7};
  su.rotate3(input, k);
  printVec("output3", input);
}
